1. Field of the Invention
The invention relates generally to the field of digital halftoning. More particularly, the invention relates to a method and apparatus for digital halftoning that provides flexibility in terms of pattern choices by enabling a position in the threshold matrix to make multiple transitions between on (e.g., printed with toner/ink) and off (e.g., not printed) thereby allowing visually displeasing patterns to be avoided without loss of gray levels
2. Description of the Related Art
Image processing apparatus and processes are evaluated in part, by their capability of delivering a complete gray scale at normal viewing distances. This capability is to a certain extent based upon the halftoning techniques employed. Halftoning is a widely used mechanism for converting input pixels represented with multiple bits of information (usually 8 bits) into bilevel picture elements (“pels”). The goal in halftoning continuous-tone images or multi-level computer generated graphics is to give an illusion of the many shades contained in the original or interpolated multi-bit values per component sample while using only one bit per sample. One traditional technique for halftoning is to create a threshold matrix (usually a different one for each color component) and use it to select a threshold value per sample. The threshold matrix is generally of much smaller dimensions than the image. Halftoning is accomplished by progressing through the input line and the threshold matrix simultaneously, comparing each input gray value with the corresponding threshold value in the threshold matrix. If the input gray value is greater than or equal to the threshold value, a black (i.e., fully saturated) corresponding output pel is generated, otherwise the corresponding output pel is white. For each line in the image, a given threshold matrix row is cycled through repetitively. The next row is used for the next line. After the last row in the threshold matrix is used, the top row of the threshold matrix is used again.
These threshold matrices are generally referred to as “supercells.” An exemplary supercell and its relationship to basic cells are discussed briefly with reference to FIGS. 1A and 1B. FIG. 1A illustrates the structure of a basic cell 100. In FIG. 1A, the basic cell 100 comprises a 4×4 pel matrix. As described further below, at present, element positions within the basic cell structure 100 are manipulated in a sequential manner (as indicated by the numbers within the elements) to achieve output gray levels. Incrementing from one output gray level to the next is accomplished by preserving the current pattern represented by the elements of the basic cell structure 100 and turning on one additional element.
FIG. 1B illustrates an exemplary supercell that is made up of much smaller basic cells such as that depicted in FIG. 1A. The four quadrants of the supercell are labeled to show the order in which the basic cells are filled. In this example, the supercell 150 comprises four basic cells 151–154. The basic cells 151–154 set the halftone's lines per inch thereby determining the level of detail that may be preserved while the size of the supercell 150 determines the number of shades obtainable. According to the current state of the art, a single halftone threshold matrix is used to convert grayscale images and graphics into binary images. The density of the pels in a region is indicative of the original values in that region.
FIG. 1C illustrates using four basic cells to achieve 64 levels by incrementally filling the basic cells in accordance with the ordering of FIG. 1B. If the input image only had 65 levels, i.e., 0 to 64, then FIG. 1C could represent a traditional threshold matrix. Each element contains the comparison, i.e., threshold, value used to determined whether to print the corresponding position in the input image or not. For purposes of this application, the convention of the input value being greater than or equal to the comparison value is employed for the output to be a one (e.g., printed). Of course, this convention is arbitrary and other conventions may be employed. For example, an alternative convention would be to enable (e.g., print) the output pel when the input value is less than or equal to the threshold value.
As illustrated by the prior art basic pattern growth example of FIG. 2, N×M+1 output gray levels may be represented with an N×M halftone matrix. For example, a 4×4 halftone matrix allows the generation of 17 levels, i.e., white 201 plus 16 other levels 202–217, to be achieved by turning one and only one element on for each subsequent level. Currently, subsequent gray levels are generated based upon previous gray levels by turning one and only one additional element on, thereby requiring patterns for each subsequent gray level to be a superset of those patterns corresponding to preceding gray levels. For example, once element 220 of the pattern is turned on, it remains on for the rest of the basic patterns. As a result, it can be difficult to avoid bad patterns, such as those that produce visual artifacts and/or undesirable textures or are otherwise visually displeasing, while also seeking to maximize the number of gray levels.